import java.util.LinkedList;
import java.util.Queue;

class Solution {
    // 该题是BFS经典类型题
    // 利用BFS来解决问题 （一层一层，上下左右）

    // 7.创建全局变量 上、下、左、右
    int[] dx = new int[]{0, 0, -1, 1};
    int[] dy = new int[]{-1, 1, 0, 0};

    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        // 1.拿到给的初始像素值（利用数轴下标的方式）
        int prev = image[sr][sc];
        // 2.初始像素和修改后的像素做对比
        if (prev == color) {
            return image;
        }

        int m = image.length, n = image[0].length;
        // 3.创建一个队列
        Queue<int[]> q = new LinkedList<>();// int[0] 横坐标 int[1] 纵坐标
        // 4.将初始像素值入队列
        q.offer(new int[]{sr, sc});

        // 5.利用BFS来解决问题(模版)
        while (!q.isEmpty()) {
            int[] tmp = q.poll();
            int a = tmp[0], b = tmp[1];// 横纵坐标
            image[a][b] = color;//进行颜色填充
            // 6.上下左右四个方向进行入队（利用数轴的方式比较简便）
            for (int i = 0; i < 4; i++) {
                int x = a + dx[i], y = b + dy[i];
                //进行判断
                if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev) {
                    q.offer(new int[]{x, y});
                }
            }
        }
        return image;
    }
}